1. Field
Example embodiments relate to a path planning apparatus smoothing a motion path while satisfying a constraint, and a method and computer-readable medium thereof.
2. Description of the Related Art
In general, a mechanical device which performs motion similar to human motion using an electrical or magnetic mechanism is called a robot. Early robots included manipulators used for automated or unmanned tasks in manufacturing plants or industrial robots such as transportation robots. Robots also performed dangerous tasks, repetitive tasks or tasks requiring a large amount of force. Recently, research has been actively conducted into a humanoid robot, which has joints similar to those of a human, and coexists with a human in a working and living space of the human and to provide various services.
Such a humanoid robot performs tasks using a manipulator which may move similar to the arm or hand motion of a human using an electrical or mechanical mechanism. In most manipulators which are currently in use, several links are connected to each other. A connection portion between the links is called a joint. The motion characteristics of the manipulator are determined according to a geometrical relationship. Mathematical representation of such a geometrical relationship is called kinematics. In general, the manipulator moves an end effector of a robot with such kinematic characteristics in a direction (goal point) to perform a task.
In order to allow the manipulator to perform a given task (e.g., grasp an object), it is important to generate a motion path of the manipulator from an initial position (start point) before the manipulator performs a task to a final position (goal point) where the task may be performed, for example, where an object may be grasped. An example of a sampling based path planning method of planning a path to connect a start point and a goal point while satisfying a constraint such as collision avoidance where a manipulator does not collide with an obstacle within a working area includes a Rapidly-exploring Random Tree (RRT) algorithm.
The RRT algorithm uses a randomly sampled configuration in a Configuration Space (C-Space), where a manipulator or a humanoid robot performs a task. An example of the RRT algorithm includes a method of repeating a process of selecting a closest node from an initial start point to extend a tree and searching for a motion path to find a goal point. A node having a smallest goal score is selected from the tree using a goal function composed of a function of a distance from the goal point to an end-effector and a directional vector to extend the tree.
However, in the RRT algorithm of the related art, when a closest node is selected to extend a tree to reach a final goal point, the tree is extended to satisfy a given goal score condition and avoid obstacles. In this case, since the tree may substantially extend in a vertical direction, a detour or zigzag path may be unnecessarily generated. Accordingly, a motion distance of a manipulator or a humanoid robot is increased and the motion of the manipulator or the humanoid robot may be rapidly changed.